// https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* nextReversed = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;
        return nextReversed;
    }

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummyNode = new ListNode(-1, head);

        ListNode* prev = nullptr;
        ListNode* tail = nullptr;
        ListNode* leftNode = nullptr;
        ListNode* rightNode = nullptr;
        ListNode* curr = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            curr = curr->next;
        }
        prev = curr;
        leftNode = curr->next;

        for (int i = 0; i < right - left + 1; i++) {
            curr = curr->next;
        }
        tail = curr->next;
        rightNode = curr;
        rightNode->next = nullptr;

        ListNode* p = reverse(leftNode);

        prev->next = p;
        curr = p;
        while (curr->next) {
            curr = curr->next;
        }
        curr->next = tail;
        
        return dummyNode->next;
    }
};